package il.technion.math.zipfdistribution;

import java.security.SecureRandom;
import java.util.Random;
import java.util.TreeSet;

public class EfficentZipfDistribution {
	private final double Alpha;
	private final int Size;
	private double sum;
	private final Random rnd;
	private final TreeSet<IndexedDouble> discreeteData;

	public EfficentZipfDistribution(final double alpha, final int size) {
		this.Alpha = alpha;
		this.Size = size;

		this.rnd = new SecureRandom();

		this.discreeteData = new TreeSet<IndexedDouble>();
		GenerateData();
	}

	public EfficentZipfDistribution(final double alpha, final int size, final long seed) {
		this.Alpha = alpha;
		this.Size = size;

		this.rnd = new Random(seed);

		// new SecureRandom()
		// //rnd.setSeed(seed);

		this.discreeteData = new TreeSet<IndexedDouble>();
		GenerateData();
	}

	public double getRate(final int i) {
		return 1 / (Math.pow(i, this.Alpha) * this.sum);
	}

	private void GenerateData() {
		// calculate total sum;
		this.sum = 0;
		final Double[] partialSums = new Double[this.Size + 1];
		final Double[] partialValues = new Double[this.Size + 1];
		double y;
		double t;
		double c = 0.0;

		// KahanSum(input)
		// double sum = 0.0
		// double c = 0.0 //A running compensation for lost low-order bits.
		// for i = 1 to input.length do
		// y = input[i] - c //So far, so good: c is zero.
		// t = sum + y //Alas, sum is big, y small, so low-order digits of y are
		// lost.
		// c = (t - sum) - y //(t - sum) recovers the high-order part of y;
		// subtracting y recovers -(low part of y)
		// sum = t //Algebraically, c should always be zero. Beware eagerly
		// optimising compilers!
		// Next time around, the lost low part will be added to y in a fresh
		// attempt.
		// return sum
		for (int n = 1; n < this.Size + 1; n++) {
			partialValues[n] = (1.0 / Math.pow(n, this.Alpha));
			y = partialValues[n] - c;
			t = this.sum + y;
			c = (t - this.sum) - y;
			this.sum = t;
			partialSums[n] = this.sum;
		}
		// Populate the tree set:
		this.discreeteData.add(new IndexedDouble(0.0, 1));
		for (int n = 2; n < this.Size; n++)
			this.discreeteData.add(new IndexedDouble((partialSums[n - 1]), n));

	}

	public int Sample() {
		final Double sample = this.rnd.nextDouble();
		final IndexedDouble chosen = this.discreeteData.lower(new IndexedDouble(sample * this.sum, -1));
		return chosen.index;

	}
	public double getSum() {
		return this.sum;
	}
	public double setSum(final double sum) {
		return this.sum = sum;
	}

	public double getAlpha() {
		return this.Alpha;
	}

	public double getSize() {
		return this.Size;
	}

}
